\chapter{使用C++语言描述数据结构}

\section{C++与C语言描述数据结构时的区别}
  C++语言的三个语言特性是：封装、继承、多态。因此与使用C语言描述、实现数据结构相比，
  使用C++的好处是可以更好的对数据结构进行抽象封装、提供更简洁的操作接口。

以顺序表数据结构为例，C与C++语言对顺序表数据结构进行描述的分别如代码\ref{lst:seqadt_c}及\ref{lst:seqadt_cpp}所示。

以创建顺序表操作为例，C语言中使用\lstinline{SeqList createSeqList(SIZE_T length);}方法，该方法签名中，参数类型为\lstinline{SIZE_T}；返回值为\lstinline{SeqList}类型。而C++语言中使用\lstinline{SeqList(SIZE_T length);}构造函数来完成顺序表创建工作，且该方法无返回值。

对于其他操作接口而言，C语言描述顺序表与C++语言描述顺序表的差别，则体现在如下几方面：
\begin{itemize}
  \item C语言描述的接口中比C++描述的接口中多一个顺序表类型参数\lstinline{SeqList list}，例如：\lstinline{void printSeqList(SeqList list);}(C语言)和\lstinline{void print();}，这主要源于C++所隐式使用的\lstinline{this}指针；
  
  \item C++方法命名比C方法命名简单，不必加后缀用于区分方法对应数据结构类型，例如\lstinline{SIZE_T lengthSeqList();}(C语言)和\lstinline{SIZE_T length();}，因为C++中，类对象使用成员访问运算符访问类的接口及成员；
  \begin{lstlisting}[frame=none, numbers=none]
  SeqList list(5);
  list.length();
  \end{lstlisting}
\end{itemize}

\begin{lstlisting}[caption=C语言描述顺序表, label=lst:seqadt_c]
typedef int ELEMTYPE;
typedef int POSITION;
typedef int SIZE_T;

struct SQList {
  ELEMTYPE *elements;
  SIZE_T length;
  SIZE_T maxNum;
};

typedef struct SQList *SeqList;

SeqList createSeqList(SIZE_T length);
void destroySeqList(SeqList list);

void printSeqList(SeqList list);
SIZE_T lengthSeqList(SeqList list);

int getVertexSeqList(SeqList list, POSITION p, ELEMTYPE *x);
POSITION locateVertexSeqList(SeqList list, ELEMTYPE x);

int insertPreSeqList(SeqList list, POSITION p, ELEMTYPE x);
int insertPostSeqList(SeqList list, POSITION p, ELEMTYPE x);
int appendElemSeqList(SeqList list, ELEMTYPE x);

int deleteElemSeqList(SeqList list, ELEMTYPE x);
int deleteVertexSeqList(SeqList list, POSITION p);
\end{lstlisting}

\begin{lstlisting}[caption=C++语言描述顺序表, label=lst:seqadt_cpp]
typedef int ELEMTYPE;
typedef int POSITION;
typedef int SIZE_T;

class SeqList {
  private:
    ELEMTYPE *elements;
    SIZE_T length;
    SIZE_T maxNum;
  
  public:
    SeqList(SIZE_T length);
    ~SeqList();

    void print();
    SIZE_T length();

    int getVertex(POSITION p, ELEMTYPE *x);
    POSITION locateVertex(ELEMTYPE x);

    bool insertPre(POSITION p, ELEMTYPE x);
    bool insertPost(POSITION p, ELEMTYPE x);
    bool appendElem(ELEMTYPE x);

    bool deleteElem(ELEMTYPE x);
    bool deleteVertex(POSITION p);
    //...
};
\end{lstlisting}

\section{C++ this指针带来的便利}
C++提供了this指针的方式可用于访问当前类对象的成员，以下以\lstinline{void print()}方法为例，介绍this指针的使用。
\begin{lstlisting}[caption={C++ this指针使用举例}, label=lst:cpp_this]
...
void SeqList::print()
{
    for (int i = 0; i < this->n; ++i)
      cout << this->elements[i] << " ";
    cout << endl;
}
...
\end{lstlisting}

\section{使用C++，我们需要考虑更多}

乍看起来，使用C++语言描述数据结构比使用C语言要方便、简单。其实，我们需要考虑得更多，
例如是否需要实现拷贝构造函数(copy constructor)、重载赋值运算符\footnote{当类的成员变量中涉及到对指针操作时，我们必然要实现拷贝构造函数以及赋值运算符。}、重载输入输出运算符等。

代码\ref{lst:cpp_more}用于测试代码\ref{lst:seqadt_cpp}描述的顺序表。需要注意的是，代码\ref{lst:seqadt_cpp}并没有实现本节所讲的拷贝构造函数、赋值运算符等。

\begin{lstlisting}[caption=测试赋值运算符, label=lst:cpp_more]
  ...
  SQList palist(10);

  palist.appendElem(1);
  palist.appendElem(2);
  palist.appendElem(3);

  SQList pblist(5);

  pblist = palist;

  pblist.print();
  palist.print();

  pblist.deleteVertex(0);
  palist.insertPre(1, -5);
  pblist.print();
  palist.print();
...
\end{lstlisting}

代码运行的结果如所示。从代码\ref{lst:cpp_more}可知，程序创建了2个顺序表对象
\lstinline{palist}和\lstinline{pblist}。在执行完上述代码后，\lstinline{pblist}
应包含2, 3两个元素，而\lstinline{palist}应包含1, -5, 2, 3三个元素。
但从程序执行结果来看，\lstinline{pblist}包含的元素是2, -5；\lstinline{palist}包含的元素是2, -5, 3, -1073741824三个元素。

\begin{verbatim}
1 2 3 
1 2 3 
2 -5 
2 -5 3 -1073741824
\end{verbatim}

为什么会是这样一个结果？这就是默认赋值运算符与默认拷贝构造函数引起的问题。C++为类提供了默认的赋值运算符及默认拷贝构造函数。默认的赋值运算符及拷贝构造函数仅仅做``值拷贝''。例如，对于代码\ref{lst:df_assignment}所示的类A而言，其有3个成员变量x,y,z；则在执行语句\lstinline{a1 = b1}时，默认赋值运算符做的事是将b1对象的成员x,y,z的值赋值给a1对象的成员x,y,z。

当一个类对象包含的成员变量类型为非指针类型时，通常而言，默认赋值运算符执行的``值拷贝''并不会出现问题。但当默认赋值运算符对指针类型成员变量做``值拷贝''时，赋值运算符左值中指针类型成员变量的值将与赋值运算符右值运算符指针类型成员变量的值相等。这意味着两个指针类型成员变量指向了同一内存地址，而后续任何操作，两者均操作同一内存地址，这便是导致代码\ref{lst:cpp_more}得到错误结果的原因。对于默认赋值运算执行``值拷贝''操作，可由图\ref{fig:df_assignment_1}表示。

\begin{lstlisting}[caption=非指针类型作为类成员变量, label=lst:df_assignment]
class A {
  private:
    int x;
    float y;
    char z;
  ...
};

A a1, b1;
...
a1 = b1;
\end{lstlisting}

\begin{figure}[thp]
  \label{fig:df_assignment_1}
  \centering
  \caption{默认赋值运算符对类对象中非指针类型成员变量进行``值拷贝''}
  \includegraphics[width=0.7\textwidth]{images/app01/df_assignment_1.eps}
\end{figure}

\begin{lstlisting}[caption=指针类型作为类成员变量, label=lst:df_assignment]
class A {
  private:
    int x;
    float y;
    char z;
    char *p;
  ...
};

A a1, b1;
...
a1 = b1;
\end{lstlisting}

\begin{figure}[thp]
  \label{fig:df_assignment_2}
  \centering
  \caption{默认赋值运算符对类对象中含指针类型成员变量进行``值拷贝''}
  \includegraphics[width=0.7\textwidth]{images/app01/df_assignment_2.eps}
\end{figure}